package Ch_2_3_Quicksort;

public class Practise_2_3_10 {
    public static void main(String[] args) {
        /*
         * 根据切比雪夫不等式 : P{ |X - u| >= kQ } <= 1/(k^2)
         * 
         * 即描述为随机变量 X 偏离均值的距离超过 k 倍标准差的概率的上界是 1/(k^2)
         * 也可以描述为随机变量 X 偏离均值的距离在 k 倍标准差内的概率的下界是 1 - 1/(k^2)
         * 
         * 我们知道 快速排序的平均比较次数 ~2NlnN 标准差为 0.65N
         * 因此假如 N = 100万，求快速排序比较次数超过 1000亿 次的概率为
         * 
         * P { |X - 2NlnN| >= 10^11 } <= 1/(k^2)
         * 
         * 那么我们只需要求出 k 就可以，由于 0.65Nk = 10^11 ==> k = 10^7/65
         * 
         * 因此 P { |X - 2NlnN| >= 10^11 } <= 4225/(10^14) 
         * 
         * 我们可以得到，这个概率的上界为 0.00000000004225
         * 
         * 也就是说真实的概率还要比这个值更小
         */
    }
}
